A vendor has multiple products for sale and a single buyer to sell them to. What pricing strategies should the vendor employ to maximize revenue? Should he set a separate take-it-or-leave-it price on each item, offer to sell all the items together at a special bundle price, or something even more complex? Such multi-dimensional mechanism design problems are notoriously poorly understood. Consider the following setting, which is perhaps the simplest imaginable beyond selling a single item: the buyer has additive value across items, and the value for each of the items is independently distributed. Hart and Nisan (2012) showed that, even in this extremely simple setting, neither selling each item separately nor selling only the bundle of all items (at their respectively optimal prices) obtains a constant approximation to the revenue of the optimal deterministic mechanism.
We will show that, for all instances, either selling each item separately *or* selling only the grand bundle achieves a constant fraction of the optimal revenue obtainable by a deterministic mechanism. Such a pricing strategy can be very easily computed from the value distributions. We conjecture that this guarantee also holds against all randomized mechanisms, as well.
Joint work with Moshe Babaioff, Nicole Immorlica, and Matt Weinberg.